package reviewAlgorithms.search;

public class NumIslands {
    public static void main(String[] args) {
        char[][] grid = {{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};
        int num = numIslands(grid);
        System.out.println(num);
    }
    public static int numIslands(char[][] grid) {
        if (grid == null || grid.length < 1){
            return 0;
        }
        int count = 0;
        int rowsNum = grid.length;
        int columnNum = grid[0].length;
        int maxNum = rowsNum * columnNum;
        int[][] state = new int[rowsNum][columnNum];
        for (int i = 0; i < maxNum; i++) {
            int row = i / columnNum;
            int column = i % columnNum;
            if (grid[row][column] == '1' && state[row][column] == 0){
                searchIsland(row,column,grid,state);
                count ++;
            }
        }

        return count;
    }

    private static void searchIsland(int row, int column, char[][] grid, int[][] state) {
        if (row < 0 || column < 0 || row >= grid.length || column >= grid[0].length || state[row][column] == 1 || grid[row][column] == '0'){
            return;
        }

        state[row][column] = 1;
        searchIsland(row - 1,column,grid,state);
        searchIsland(row + 1,column,grid,state);
        searchIsland(row,column - 1,grid,state);
        searchIsland(row,column + 1,grid,state);

    }
}
